/**
 * 正则表达式匹配
 *
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 *
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
 */


/**
 * 注意是涵盖字符, 意思就是要完全一样!!!!!!! 刚开始没明白项链好久!!!!!!!!
 * 1. 动态规划
 * 咱要知道这题为啥要用动态规划, 可能因为涉及到字符串的涵盖问题了, 遇到这种问题要多往动态规划上思考;
 * 理解了这题的转态表示就好做了, dp[i][j] : s 的 0~i, 是否涵盖在 p 的 0~j 中
 * 下面得我废话不多说, 直接看代码
 * 时间复杂度 : O(n^2)
 * 空间复杂度 : O(n^2)
 */

public class Main {
    public boolean isMatch(String s, String p) {

        // 分别求出 s, p 的长度
        int m = s.length(), n = p.length();

        // 在 s, 和 p前面分别加上一个空字符, 用来完成下标的对应关系
        // 这里不是因为在判断 '*' 时要王前面判断一个, 因为题目明确规定了
        // '*'前面一定是一个可以与之匹配的字符, 所以不用担心越界
        s = " " + s;
        p = " " + p;
        // 这里不用修改 m和 n, 因为正好与 dp数组对应


        // 定于 动态数组dp, 记录转态表示
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 要记得初始化, 在 s 和 p 没有字符的时候, 直接为 true
        dp[0][0] = true;

        // 当 s 为空时, 还有一种可能使 p 能匹配, 也就是 * 每隔两个出现一次, 因为这样正好可以将 p 匹配为空串
        for (int i = 2; i <= n; i += 2) {

            if (p.charAt(i) == '*') dp[0][i] = true;
            // 一旦没有出现就退出初始化了
            else break;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char c = p.charAt(j);
                if (c == '.') {

                    // 因为 '.' 可以匹配任意字符, 所以直接匹配成功, 这时这个位置是否为true, 就看前面
                    // 的 p是否可以涵盖 已经出现的所有 s了
                    dp[i][j] = dp[i - 1][j - 1];

                } else if (c == '*') {

                    // 匹配到 '*' 要判断前面一个字符是什么
                    // 能匹配到这里, 都不会越界, 题目规定的
                    char cc = p.charAt(j - 1);

                    if (cc == '.') {

//                           (不知道啥原因, 可能题目的题意有点问题, 这里匹配不了)
//                        // 若前面是 '.' 直接可以宣布游戏结束, 因为 ".*" 可以匹配任意多个 '.', 直接成功涵盖
//                        // 直接就是大 boss 了, 直接演都不用演了
//                        return true;

                        // 匹配空串
                        dp[i][j] = dp[i][j - 2];

                        // 匹配一个或多个 '.'
                        dp[i][j] |= dp[i - 1][j];

                    } else {

                        // 前面是普通字符
                        // 这里又要分情况讨论
                        // 可以带前面的字符一起匹配成空串, 相当于直接浪费两个 p的字符
                        // 且这种情况永远存在, 所以要把另外的情况的最终结果与之 |=, 有 true就为 true
                        dp[i][j] = dp[i][j - 2];

                        // 不匹配空串
                        // 可以匹配一个前面的字符, 因为可以匹配多个字符, 就可以相当于匹配完之后
                        // 这两个原封不动, s的字符减一, 但这个前提是 s的当前字符与 p的相同
                        dp[i][j] |= (s.charAt(i) == cc && dp[i - 1][j]);

                    }
                } else {

                    // 如果为普通字符串
                    // 比较是否相同
                    if (s.charAt(i) == c) {

                        // 相同就和之前的 '.' 一样
                        dp[i][j] = dp[i - 1][j - 1];

                    }
                }
            }
        }

        // 返回结果
        return dp[m][n];
    }


    // *****************************************
    // 代码优化, 将代码重新组合

    public boolean isMatch1(String s, String p) {
        int m = s.length(), n = p.length();
        s = " " + s;
        p = " " + p;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 2; i <= n; i += 2) {
            if (p.charAt(i) == '*') dp[0][i] = true;
            else break;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j) == '*') dp[i][j] = dp[i][j - 2] || (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.') && dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Main test = new Main();
        System.out.println(test.isMatch("ab", ".*c"));
    }
}